function lengthOfLIS(nums) {
  let len = nums.length;
  if (!len) return 0;
  let dp = nums(len).fill(1);
  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
}

function lengthOfLIS(nums) {
  let len = nums.length;
  if (!len) return 0;
  let res = [nums[0]];
  for (let i = 1; i < nums.length; i++) {
    let lastItem = res[res.length - 1];
    if (nums[i] > lastItem) {
      res.push(nums[i]);
    } else {
      let left = 0;
      let right = res.length - 1;
      while (left < right) {
        let mid = (left + right) >> 1;
        if (nums[i] > res[mid]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      res[left] = nums[i];
    }
  }
  return res.length;
}

function indexOfLIS(nums) {
  let len = nums.length;
  if (!len) return 0;
  let res = [0];
  let prev = [undefined];
  for (let i = 1; i < len; i++) {
    let lastItem = nums[res[res.length - 1]];
    if (nums[i] > lastItem) {
      prev[i] = res[res.length - 1];
      res.push(i);
    } else {
      let left = 0;
      let right = res.length - 1;
      while (left < right) {
        let mid = (left + right) >> 1;
        if (nums[res[mid]] < nums[i]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      res[left] = i;

      if (left === 0) {
        prev[i] = undefined;
      } else {
        prev[i] = left - 1;
      }
    }
  }

  let resLen = res.length;
  let prevIndex = res[resLen - 1];
  while (resLen > 0) {
    resLen--;
    res[resLen] = prevIndex;
    prevIndex = prev[prevIndex];
  }

  return res;
}
